// Copyright 2012 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/ic/stub-cache.h"

#include "src/ast/ast.h"
#include "src/base/bits.h"
#include "src/counters.h"
#include "src/heap/heap-inl.h" // For InYoungGeneration().
#include "src/ic/ic-inl.h"

namespace v8 {
namespace internal {

    StubCache::StubCache(Isolate* isolate)
        : isolate_(isolate)
    {
        // Ensure the nullptr (aka Smi::kZero) which StubCache::Get() returns
        // when the entry is not found is not considered as a handler.
        DCHECK(!IC::IsHandler(MaybeObject()));
    }

    void StubCache::Initialize()
    {
        DCHECK(base::bits::IsPowerOfTwo(kPrimaryTableSize));
        DCHECK(base::bits::IsPowerOfTwo(kSecondaryTableSize));
        Clear();
    }

    // Hash algorithm for the primary table.  This algorithm is replicated in
    // assembler for every architecture.  Returns an index into the table that
    // is scaled by 1 << kCacheIndexShift.
    int StubCache::PrimaryOffset(Name name, Map map)
    {
        STATIC_ASSERT(kCacheIndexShift == Name::kHashShift);
        // Compute the hash of the name (use entire hash field).
        DCHECK(name->HasHashCode());
        uint32_t field = name->hash_field();
        // Using only the low bits in 64-bit mode is unlikely to increase the
        // risk of collision even if the heap is spread over an area larger than
        // 4Gb (and not at all if it isn't).
        uint32_t map_low32bits = static_cast<uint32_t>(map.ptr() ^ (map.ptr() >> kMapKeyShift));
        // Base the offset on a simple combination of name and map.
        uint32_t key = map_low32bits + field;
        return key & ((kPrimaryTableSize - 1) << kCacheIndexShift);
    }

    // Hash algorithm for the secondary table.  This algorithm is replicated in
    // assembler for every architecture.  Returns an index into the table that
    // is scaled by 1 << kCacheIndexShift.
    int StubCache::SecondaryOffset(Name name, int seed)
    {
        // Use the seed from the primary cache in the secondary cache.
        uint32_t name_low32bits = static_cast<uint32_t>(name.ptr());
        uint32_t key = (seed - name_low32bits) + kSecondaryMagic;
        return key & ((kSecondaryTableSize - 1) << kCacheIndexShift);
    }

    int StubCache::PrimaryOffsetForTesting(Name name, Map map)
    {
        return PrimaryOffset(name, map);
    }

    int StubCache::SecondaryOffsetForTesting(Name name, int seed)
    {
        return SecondaryOffset(name, seed);
    }

#ifdef DEBUG
    namespace {

        bool CommonStubCacheChecks(StubCache* stub_cache, Name name, Map map,
            MaybeObject handler)
        {
            // Validate that the name and handler do not move on scavenge, and that we
            // can use identity checks instead of structural equality checks.
            DCHECK(!Heap::InYoungGeneration(name));
            DCHECK(!Heap::InYoungGeneration(handler));
            DCHECK(name->IsUniqueName());
            DCHECK(name->HasHashCode());
            if (handler->ptr() != kNullAddress)
                DCHECK(IC::IsHandler(handler));
            return true;
        }

    } // namespace
#endif

    void StubCache::Set(Name name, Map map, MaybeObject handler)
    {
        DCHECK(CommonStubCacheChecks(this, name, map, handler));

        // Compute the primary entry.
        int primary_offset = PrimaryOffset(name, map);
        Entry* primary = entry(primary_, primary_offset);
        MaybeObject old_handler(primary->value);

        // If the primary entry has useful data in it, we retire it to the
        // secondary cache before overwriting it.
        if (old_handler != MaybeObject::FromObject(isolate_->builtins()->builtin(Builtins::kIllegal)) && primary->map != kNullAddress) {
            Map old_map = Map::cast(Object(primary->map));
            int seed = PrimaryOffset(Name::cast(Object(primary->key)), old_map);
            int secondary_offset = SecondaryOffset(Name::cast(Object(primary->key)), seed);
            Entry* secondary = entry(secondary_, secondary_offset);
            *secondary = *primary;
        }

        // Update primary cache.
        primary->key = name.ptr();
        primary->value = handler.ptr();
        primary->map = map.ptr();
        isolate()->counters()->megamorphic_stub_cache_updates()->Increment();
    }

    MaybeObject StubCache::Get(Name name, Map map)
    {
        DCHECK(CommonStubCacheChecks(this, name, map, MaybeObject()));
        int primary_offset = PrimaryOffset(name, map);
        Entry* primary = entry(primary_, primary_offset);
        if (primary->key == name.ptr() && primary->map == map.ptr()) {
            return MaybeObject(primary->value);
        }
        int secondary_offset = SecondaryOffset(name, primary_offset);
        Entry* secondary = entry(secondary_, secondary_offset);
        if (secondary->key == name.ptr() && secondary->map == map.ptr()) {
            return MaybeObject(secondary->value);
        }
        return MaybeObject();
    }

    void StubCache::Clear()
    {
        MaybeObject empty = MaybeObject::FromObject(
            isolate_->builtins()->builtin(Builtins::kIllegal));
        Name empty_string = ReadOnlyRoots(isolate()).empty_string();
        for (int i = 0; i < kPrimaryTableSize; i++) {
            primary_[i].key = empty_string.ptr();
            primary_[i].map = kNullAddress;
            primary_[i].value = empty.ptr();
        }
        for (int j = 0; j < kSecondaryTableSize; j++) {
            secondary_[j].key = empty_string.ptr();
            secondary_[j].map = kNullAddress;
            secondary_[j].value = empty.ptr();
        }
    }

} // namespace internal
} // namespace v8
